package com.cdream.basic.algorithm.leetcode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 加权图最短路径，包括Floyd, Dijkstra 算法
 * 算法示例取自 leetcode-743 https://leetcode-cn.com/problems/network-delay-time/
 */
public class WeightedGraphShortestPath {
    /**
     * floyd 最短路径算法，又名插点法。计算加权图中多源点最短路径问题
     */
    public int floyd(int[][] times, int n, int k) {
        int INF = Integer.MAX_VALUE / 2;
        int[][] distance = new int[n + 1][n + 1];
        for (int[] ints : distance) {
            Arrays.fill(ints, INF);
        }

        for (int[] time : times) {
            int x = time[0];
            int y = time[1];
            distance[x][y] = time[2];
        }
        // 经过的顶点 1~i,从x到y的最小值
        for (int i = 1; i <= n; i++) {
            for (int x = 1; x <= n; x++) {
                for (int y = 1; y <= n; y++) {
                    if (x == y) {
                        distance[x][y] = 0;
                    } else {
                        distance[x][y] = Math.min(distance[x][i] + distance[i][y], distance[x][y]);
                    }
                }
            }
        }
        int res = -1;
        for (int i = 1; i < distance[k].length; i++) {
            res = Math.max(res, distance[k][i]);
        }
        return res == INF ? -1 : res;
    }

    public int dijkstra(int[][] times, int n, int k) {
        int INF = Integer.MAX_VALUE / 2;
        int[][] distance = new int[n + 1][n + 1];
        for (int[] ints : distance) {
            Arrays.fill(ints, INF);
        }

        for (int[] time : times) {
            int x = time[0];
            int y = time[1];
            distance[x][y] = time[2];
        }

        int[] res = new int[n + 1];
        boolean[] used = new boolean[n + 1];
        Arrays.fill(res, INF);
        res[k] = 0;
        // 注意这里不能把used[k]置为true, 因为要初始化k到所有点的最小距离， 并且for循环少一个，最后会少一个抛出空指针异常
        used[k] = true;
        for (int i = 1; i <= n; i++) {
            // 找到距k最近的点
            int x = -1;
            for (int i1 = 1; i1 <= n; i1++) {
                if (!used[i1] && (x == -1 || res[i1] < res[x])) {
                    x = i1;
                }
            }
            used[x] = true;
            // 当确定最小值加入后，更新未确定集合最小值
            for (int i1 = 1; i1 <= n; i1++) {
                // 最大超不过INF
                res[i1] = Math.min(res[i1], res[x] + distance[x][i1]);
            }
        }
        res[0] = -1;
        int ans = Arrays.stream(res).max().getAsInt();
        return ans == INF ? -1 : ans;
    }

    public int dijkstra2(int[][] times, int n, int k) {
        int INF = Integer.MAX_VALUE / 2;
        Map<Integer, List<int[]>> distanceMap = Arrays.stream(times).collect(Collectors.groupingBy(a -> a[0]));


        int[] res = new int[n + 1];
        Arrays.fill(res, INF);
        res[k] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.<int[]>comparingInt(a -> a[0]).thenComparing(a -> a[1]));
        pq.add(new int[]{k, 0});
        while (!pq.isEmpty()) {
            int[] poll = pq.poll();
            // 如果到当前poll[0]的最小距离小于经过poll[1]，直接返回
            int fromNode = poll[0];
            if (res[fromNode] < poll[1]) {
                continue;
            }
            List<int[]> nextNodes = distanceMap.getOrDefault(fromNode, new ArrayList<>());
            for (int[] nextNode : nextNodes) {
                //如果经过当前节点，从当前接点到目标节点距离小于原距离
                int toNode = nextNode[1];
                int fromToDistance = nextNode[2];

                if (res[fromNode] + fromToDistance < res[toNode]) {
                    res[toNode] = res[fromNode] + fromToDistance;
                    pq.offer(new int[]{toNode, res[toNode]});
                }
            }
        }
        res[0] = -1;
        int ans = Arrays.stream(res).max().getAsInt();
        return ans == INF ? -1 : ans;
    }

    public static void main(String[] args) {
        WeightedGraphShortestPath wgsp = new WeightedGraphShortestPath();
        wgsp.dijkstra(new int[][]{{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}, 4, 2);
    }
}
